C'est une version restreinte de l'algorithme de Deutsch-Jozsa dans laquelle, au lieu de distinguer deux classes de fonctions, on essaie de retrouver une chaîne secrète encodée dans une fonction[2]. Il a été conçu pour prouver la distinction entre les classes de complexitéBQP et BPP[1].
En informatique "classique", la méthode la plus efficace pour retrouver la chaîne secrète consiste à évaluer la fonction fois avec comme valeurs d'entrée pour tout [2] :
Ensuite, appliquer l'oracle qui transforme . Cela peut être simulé au moyen de l'oracle standard qui transforme en appliquant l'oracle à ( représente une addition modulo 2).
Cela transforme la superposition en :
Une nouvelle transformée de Hadamard est appliquée à chaque qubit, de telle sorte que :
pour les qubits où , l'état est converti de à
pour les qubits où , l'état est converti de à
Pour obtenir , une mesure selon la base standard () est effectuée sur les qubits.
L'algorithme peut donc être représenté ainsi, où représente la transformée de Hadamard sur qubits :
La raison pour laquelle l'état final est est que, pour un donné :
Puisque est vrai seulement quand , cela signifie que la seule amplitude non nulle correspond à .
↑ ab et cS D Fallek, C D Herold, B J McMahon, K M Maller, K R Brown, and J M Amini, « Transport implementation of the Bernstein–Vazirani algorithm with ion qubits », New Journal of Physics, vol. 18, (DOI10.1088/1367-2630/aab341)